package com.shigi.knapsack.solvers;

import com.shigi.knapsack.KnapsackInstance;
import com.shigi.knapsack.KnapsackItem;
import com.shigi.knapsack.KnapsackSolution;
import com.shigi.knapsack.KnapsackSolver;

/**
 * Created by Miroslav Šiagi on 03/11/14.
 */
public class FPTAS implements KnapsackSolver {

    private KnapsackSolution knapsackSolution;
    private KnapsackInstance knapsackInstance;
    private KnapsackItem[] knapsackItems;
    private int neglectedBits;
    private double epsilon;

    public FPTAS(double epsilon) {
        this.epsilon = epsilon;
    }

    public KnapsackSolution solve(KnapsackInstance knapsackInstance) {
        this.knapsackInstance = knapsackInstance;
        this.knapsackItems = this.knapsackInstance.getKnapsackItems();

        this.knapsackSolution = new KnapsackSolution(knapsackInstance.getId());
        this.knapsackSolution.setNumberOfItems(knapsackInstance.getNumberOfItems());

        int CMax = 0;
        int numberOfItems = knapsackItems.length;
        for (int i = 0; i <numberOfItems; i++) {
            if(knapsackItems[i].getValue() >= CMax) {
                CMax = knapsackItems[i].getValue();
            }
        }
        this.neglectedBits = (int)Math.ceil(Math.log(this.epsilon * CMax / numberOfItems)/Math.log(2.0));

        createSolution();

        return this.knapsackSolution;
    }

    private void createSolution() {
        DynamicProgrammingValue dynamicProgrammingValue = new DynamicProgrammingValue();
        KnapsackInstance modifiedKnapsackInstance = new KnapsackInstance(this.knapsackInstance);

        //we need to alter values

        int numOfItems = this.knapsackItems.length;
        for (int i = 0; i < numOfItems; i++) {
            modifiedKnapsackInstance.getKnapsackItems()[i].setValue(this.knapsackItems[i].getValue() >> neglectedBits);
        }
        this.knapsackSolution = dynamicProgrammingValue.solve(modifiedKnapsackInstance);
        setUnmodifiedTotalValue(modifiedKnapsackInstance);
    }

    private void setUnmodifiedTotalValue(KnapsackInstance modifiedKnapsackInstance) {
        int totalValue = 0;
        int numberOfItems = this.knapsackItems.length;
        for (int i = 0; i < numberOfItems; i++) {
            if(modifiedKnapsackInstance.getKnapsackItems()[i].isUsed()) {
                totalValue += this.knapsackItems[i].getValue();
            }
        }
        this.knapsackSolution.setTotalValue(totalValue);
    }

}
